class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();

        // 算出每个数的前缀之积和后缀之积
        // [1, 2, 3, 4]
        // 2 这个位置 除自身以外数组的乘积就是1x3x4
        // 1 就是前缀积，3x4就是后缀积
        // 但是下面的代码的空间复杂度还可以再优化
        // vector<int> pre(n, 1);
        // vector<int> sub(n, 1);
        // for(int i = 1, j = n - 2; i < n && j >= 0; i++, j--)
        // {
        //     pre[i] = nums[i - 1] * pre[i - 1];
        //     sub[j] = nums[j + 1] * sub[j + 1];
        // }

        // vector<int> ans(n, 0);
        // for(int i = 0; i < n; i++)
        //     ans[i] = sub[i] * pre[i];
        // return ans;


        // 下面是优化完空间复杂度为O(1)的情况，因为题目中说了输出数组不算做额外空间
        // 所以我们可以使用这个数组来搞事情
        // 1. 利用这个答案数组存放前缀积
        vector<int> ans(n, 1);
        for(int i = 1; i < n; i++)
            ans[i] = ans[i - 1] * nums[i - 1];
        
        // 2. 拿一个变量记录当前的后缀积，初始化为1
        int subfixProduct = 1;
        for(int i = n - 1; i >= 0; i--)
        {
            ans[i] = ans[i] * subfixProduct;
            subfixProduct *= nums[i];   // 更新后缀积
        }
        return ans;
    }
};